package week07

// 200. 岛屿数量
// https://leetcode-cn.com/problems/number-of-islands/

func numIslands(grid [][]byte) int {
	var m, n = len(grid), len(grid[0])

	var index = func(x, y int) int {
		return x * n + y
	}

	var father = make([]int, m*n)
	for i := range father {
		father[i] = i
	}

	for x := range grid {
		for y := range grid[x] {
			if grid[x][y] == '0' {
				continue
			}
			for dir := range dx {
				nx := x + dx[dir]
				ny := y + dy[dir]
				if nx < 0 || ny < 0 || nx >= len(grid) || ny >= len(grid[0]) {
					continue
				}
				if grid[nx][ny] == '1' {
					unionSet(father, index(x, y), index(nx, ny))
				}
			}
		}
	}
	var ans = 0
	for x := range grid {
		for y := range grid[x] {
			if grid[x][y] != '0' && find(father, index(x, y)) == index(x, y) {
				ans++
			}
		}
	}
	return ans
}

func find(father []int, x int) int {
	if father[x] != x {
		father[x] = find(father, father[x])
	}
	return father[x]
}

func unionSet(father []int, x, y int) {
	father[find(father, y)] = find(father, x)
}


var dx = [4]int{0, 1, 0, -1}
var dy = [4]int{1, 0, -1, 0}